# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int, start: int = 0) -> int:
        # 二分查找即可
        if start > n:
            return start
        mid = (n + start) // 2
        if isBadVersion(mid):
            return self.firstBadVersion(start=start, n=mid-1)
        else:
            return self.firstBadVersion(start=mid+1, n=n)
